#include <bits/stdc++.h>

#define fi first
#define se second
#define pii pair<db,int>
#define pb push_back
#define vec vector<int>
#define y1 y_____hahahaha_____1

using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;

const int N = 5010;
const int M = 2e5+10;

int n,m;
db E;

struct graph{
	int h[N],cnt,pre[N];
	bool vis[N];
	db dis[N];
	graph(){memset(h,0,sizeof h); memset(pre,0,sizeof pre); memset(vis,0,sizeof vis);cnt = 0;}
	struct edge{int v;db w;int nxt;}e[M];
	void link(int x,int y,db w){e[++cnt] = (edge){y,w,h[x]};h[x] = cnt;}
	void dijk(int st){
		for(int i = 1;i <= n;i++) dis[i] = 1e18; dis[st] = 0;
		priority_queue<pii> q; q.push(pii(-dis[st],st));
		while(!q.empty()){
			pii d = q.top(); q.pop(); int x = d.se; if(vis[x]) continue; vis[x] = 1;
			for(int i = h[x],y;i;i = e[i].nxt)
				if(dis[y = e[i].v] > dis[x] + e[i].w){
					pre[y] = i; dis[y] = dis[x] + e[i].w; q.push(pii(-dis[y],y));
				}
		}
	}
}R,G;

namespace Heap{
	int rt[N],ch[M<<3][2],ncnt,dist[M<<3];
	struct node{int ed;db w;node(int e = 0,db _w = 0):ed(e),w(_w){}}val[M<<3];
	bool operator < (node x,node y){return x.w == y.w ? x.ed < y.ed : x.w < y.w;}
	int merge(int x,int y){
		if(!x || !y) return x | y;
		if(val[y] < val[x]) swap(x,y); int nd = ++ncnt;  val[nd] = val[x]; ch[nd][0] = ch[x][0]; ch[nd][1] = ch[x][1]; dist[nd] = dist[x];
		ch[nd][1] = merge(ch[nd][1],y); if(dist[ch[nd][0]] < dist[ch[nd][1]]) swap(ch[nd][0],ch[nd][1]);
		dist[nd] = dist[ch[nd][1]] + 1;
		return nd;
	}
}

using Heap :: merge;
using Heap :: rt;
using Heap :: ch;
using Heap :: val;
using Heap :: ncnt;

int main(){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	scanf("%d %d %lf",&n,&m,&E);
	for(int i = 1;i <= m;i++){
		int s,t; db e; scanf("%d %d %lf",&s,&t,&e); if(s == n) continue;
		G.link(s,t,e); R.link(t,s,e);
	}
	R.dijk(n);
	vector<pii> pot; for(int i = 1;i <= n;i++) pot.pb(pii(R.dis[i],i)); sort(pot.begin(),pot.end());
	//	vector<db> t;
	for(auto d : pot){
		int x = d.se;
		for(int i = G.h[x],y;i;i = G.e[i].nxt){
			if(i != R.pre[x]){
				y = G.e[i].v; ncnt++; val[ncnt] = Heap :: node(y,G.e[i].w - (R.dis[x] - R.dis[y])); //t.pb(val[ncnt].w);
				rt[x] = merge(rt[x],ncnt);
			}
		}
		rt[x] = merge(rt[x],rt[G.e[R.pre[x]].v]);
	}
	//	sort(t.begin(),t.end()); for(int i = 1;i <= 10000;i+=111) cerr<<t[i]<<endl;
	int cnt = 0;
	if(E >= R.dis[1]) E -= R.dis[1],/*cerr<<R.dis[1]<<endl,*/cnt++;
	else return puts("0"),0;
	priority_queue<pii,vector<pii>,greater<pii> > q; if(rt[1]) q.push(pii(val[rt[1]].w,rt[1]));//,cerr<<val[rt[1]].w<<endl;
	while(!q.empty() && E > 0){
		int x = q.top().se;db cost = q.top().fi;
		if(E >= cost + R.dis[1]) E -= cost + R.dis[1],/*cerr<<cost + R.dis[1]<<endl,*/cnt++; else break; q.pop();
		if(ch[x][0]) q.push(pii(cost - val[x].w + val[ch[x][0]].w,ch[x][0]));
		if(ch[x][1]) q.push(pii(cost - val[x].w + val[ch[x][1]].w,ch[x][1]));
		if(rt[val[x].ed]) q.push(pii(cost + val[rt[val[x].ed]].w,rt[val[x].ed]));
	}
	printf("%d\n",cnt);
	return 0;
}
